import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-15
 * Time: 10:25
 */
class Solution4_1 {
    public int[] inventoryManagement(int[] stock, int cnt) {
        //方法一：冒泡排序
        int n = stock.length;
        for(int i = 0 ; i < n ; i++){
            for(int j = n-1 ; j > i ; j--){
                if(stock[j] < stock[j-1]){
                    //把小的元素往前面放
                    swap(stock , j , j-1);

                }
            }
        }
        int[] ret = new int[cnt];
        for(int i = 0 ; i < cnt ; i++){
            ret[i] = stock[i];
        }
        return ret;
    }
    public void swap(int[] stock , int a , int b){
        int tem = stock[a];
        stock[a] = stock[b];
        stock[b] = tem;
    }


}
class Solution4_2 {
    public int[] inventoryManagement(int[] nums, int cnt) {
        //方法二：快排分三部分思想
        int l = 0 , r = nums.length-1;
        quickSort(nums,l,r);
        int[] ret = new int[cnt];
        for(int i = 0 ; i < cnt ; i++){
            ret[i] = nums[i];
        }
        return ret;
    }

    public void quickSort(int[] nums , int l , int r){
        int left = l - 1 , right = r + 1 , i = l ;
        if(l >= r){
            return;
        }
        // 在[l,r]区间进行排序
        // 产生随机数
        int index = new Random().nextInt( r - l + 1) + l;
        int key = nums[index];
        while(i < right){
            //小于的情况实际上就是，右边界和右边界元素的交换
            if(nums[i] < key){
                swap(nums,++left,i++);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,--right,i);//换过去的是未排序的元素
            }
        }
        quickSort(nums,l,left);
        quickSort(nums,right,r);
    }
    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

}
class Solution4_3 {
    public int[] inventoryManagement(int[] nums, int cnt) {
        //方法三：快排分三部分思想
        int l = 0 , r = nums.length-1;
        int k = cnt;
        quickSort(nums,l,r,k);
        int[] ret = Arrays.copyOf(nums,k);
        return ret;

    }

    public void quickSort(int[] nums , int l , int r , int k){
        int left = l - 1 , right = r + 1 , i = l ;
        if(l >= r){
            return;
        }
        // 在[l,r]区间进行排序
        // 产生随机数
        int index = new Random().nextInt( r - l + 1) + l;
        int key = nums[index];
        while(i < right){
            //小于的情况实际上就是，右边界和右边界元素的交换
            if(nums[i] < key){
                swap(nums,++left,i++);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,--right,i);//换过去的是未排序的元素
            }
        }

        //根据划分的三个部分在找
        // 三个部分的区间为[l,left]  [left+1,right-1]  [right,r]
        int a = left-l+1;
        int b = right-left-1;
        int c = r-right+1;
        if(k < a){
            quickSort(nums,l,left,k);
        }else if(k <= a + b){
            return;
        }else if(k > a + b){
            quickSort(nums,right,r,k-a-b);
        }

    }
    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

}




public class Test4 {
}
